\textbf{Aufgabe:}

Lesen Sie Abschnitt \buchmann{4.10} über die affine Chiffre und rechnen Sie ein Beispiel eines Known-Plaintext Angriffs.

\textbf{Lösung:}

Wir wählen den Schlüssel $e = (a,b) = (5,13)$ und verwenden das Alphabet $\mathrm{\Z_{26}}$. Es ist zu beachten, dass bei einem affinem Chiffre a teilerfremd zu m sein muss. Also ggt(a, m) = 1. Verschlüsselt man das Wort HALLO mit der affinen Chiffre (m = 26) im ECB-Mode, so ergibt sich.

\[
\begin{tabular}{ccccc}
H&A&L&L&O\\
\hline
7&0&11&11&14\\
22&13&16&16&5\\
\hline
W&N&Q&Q&E\\
\end{tabular}\\
\]
Ein Know-Plaintext Angriff ist nun möglich, wenn der Angreifer folgende Informationen identifiziert:
\begin{itemize}
  \item Das Alphabet $\mathrm{\{A,B,\ldots, \Z_{26}\}}$
  \item Das bei der Anwendung der affinen Chiffre mit Schlüssel (a,b) der Buchstabe \textit{H(7)} ind \textit{W(22)} und \textit{O(14)} in \textit{E(5)} verschlüsselt wird. (Es müssen mindestens zwei verschiedene Paare bekannt sein!)
\end{itemize}
Aus diesen Informationen kann der Angreifer folgende Kongruenzen aufstellen.
\begin{enumerate}
  \item $\mathrm{14a + b \equiv 5 \mod 26}$
  \item $\mathrm{7a + b \equiv 22 \mod 26}$
\end{enumerate}
Die 2. Kongruenz wird nach $\mathrm{b \equiv 22 -7a \mod 26}$ umgestellt und anschließend in die 1. Kongruenz für b eingesetzt. Daraus ergibt sich $\mathrm{14a + 22 -7a \equiv 5 \mod 26}$, ausgerechnet also $\mathrm{7a \equiv 9 \mod 26}$.

Aus $\mathrm{7a \equiv 9 \mod 26}$ wird nun die Inverse des Quotienten von $\mathrm{a \mod 26}$ berechnet. Dies ist nur möglich, wenn der Quotient teilerfremd zu 26 ist. In diesem Fall ggt(7, 26) = 1. Ist dies nicht der Fall, so hat der Angreifer Pech gehabt und muss einen anderen Datensatz abfangen.

Die Inverse wird mit Hilfe des erweiterten euklidischen Algorithmus ($\mathrm{7 \equiv 1 \mod 26}$) berechnet.

\[
\begin{tabular}{c|ccccccc}
$\mathrm{k}$&1&2&3&4&5&6&7\\\hline
$\mathrm{r_k}$&7&26&7&5&2&1&0\\
$\mathrm{q_k}$&&0&3&1&2&2\\
$\mathrm{x_k}$&1&0&1&3&4&11&26\\
$\mathrm{y_k}$&0&1&0&1&1&3&7\\
\end{tabular}\\
\]
Als Inverse erhalten wir -11. In dem wir nun $\mathrm{7a \equiv 9 \mod 26}$ mit -11 durchmultiplizieren erhalten wir $\mathrm{-77a \equiv -99 \mod 26}$. Ausgerechnet wird daraus $\mathrm{a = 5}$.\\
Um b zu berrechnen setzen wir $\mathrm{a = 5}$ in die oben umgeformte Kongruenz $\mathrm{b \equiv 22 -7a \mod 26}$. Daraus ergibt sich $\mathrm{b = 13}$.\\
Der Angreifer kennt nun unseren Schlüssel $e = (5,13)$ und kann somit jeden Text ent- und verschlüsseln.